package com.jwetherell.my.problems.backtracking;

public class NQueenProblem {

	private static int dimension = 8; // 4*4 chess board
	private int[][] chessBoard;;

	public static void main(String[] args) {
		NQueenProblem queenProblem = new NQueenProblem();
		queenProblem.initBoard();
		queenProblem.printChessBoard();

		int[] xPos = new int[dimension];
		if (queenProblem.findSolution(xPos, 0)) {
			System.out.println("Solution found");
			queenProblem.applySolution(xPos);
			queenProblem.printChessBoard();
		} else {
			System.out.println("Solution not found");
		}

	}

	private boolean findSolution(int[] xPos, int nQueensAlreadyPlaced) {
		if (nQueensAlreadyPlaced == dimension)
			return true;

		int[] possiblePositions = getPossiblePositions(xPos, nQueensAlreadyPlaced);
		for (int i = 0; i < possiblePositions.length; i++) {

			int possiblePosition = possiblePositions[i];

			xPos[nQueensAlreadyPlaced] = possiblePosition;

			if (findSolution(xPos, nQueensAlreadyPlaced + 1))
				return true;

			xPos[nQueensAlreadyPlaced] = 0; // backtracking
		}

		return false;
	}

	private int[] getPossiblePositions(int[] xPos, int nQueesnAlreadyPlaced) {
		int [] feasiblePositions = new int [dimension - nQueesnAlreadyPlaced];
		
		boolean currentXPosAttackedByOtherQueen;
		int k = 0;
		int queenXPos;
		int currentYPos = nQueesnAlreadyPlaced;
		for (int currentXPos = 0; currentXPos < dimension; currentXPos++) {
			currentXPosAttackedByOtherQueen = false;
			
			for (int queenYPos = 0; queenYPos < nQueesnAlreadyPlaced; queenYPos++) {
				
				// check if current XPos is attacked by any other queen vertically
				queenXPos = xPos[queenYPos];
				if (queenXPos == currentXPos) { // already some queen is there at this pos
					currentXPosAttackedByOtherQueen = true;
					break;
				}
				
				// find x position of both left and right diagonal of the queen at level currentYPos
				int queenLeftDiagonalXPos = queenXPos - (currentYPos - queenYPos);
				int queenRightDiagonalXpos = queenXPos + (currentYPos - queenYPos);
				
				// check if current XPos is attacked by any other queen diagonally
				if (currentXPos == queenLeftDiagonalXPos || currentXPos == queenRightDiagonalXpos) {
					currentXPosAttackedByOtherQueen = true;
					break;
				}
				
			}
			
			/*
			 *  We can place our queen at this x pos as this x pos in not attacked by any other queen both vertically
			 *   and diagonally
			 */
			if (!currentXPosAttackedByOtherQueen) {
				feasiblePositions[k] = currentXPos;
				k++;
			}
		}
		
		int [] tempFeasiblePositions = new int [k];
		for (int i = 0; i < k; i++) {
			tempFeasiblePositions[i] = feasiblePositions[i];
		}
		
		return tempFeasiblePositions;
	}

	private void initBoard() {
		chessBoard = new int[dimension][dimension];
		for (int i = 0; i < chessBoard.length; i++) {
			for (int j = 0; j < chessBoard[0].length; j++) {
				chessBoard[i][j] = 0;
			}
		}
	}

	private void printChessBoard() {
		for (int i = 0; i < chessBoard.length; i++) {
			for (int j = 0; j < chessBoard[0].length; j++) {
				if (chessBoard[i][j] >= 0 && chessBoard[i][j] <= 9)
					System.out.print(" ");
				System.out.print(chessBoard[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}

	private void applySolution(int[] xPos) {
		int yPos = 0;
		for (int i = 0; i < dimension; i++) {
			chessBoard[yPos][xPos[i]] = 1;
			yPos++;
		}
	}

}